package problems

import (
	"bytes"
	"fmt"
	"math"
	"sort"
	"strconv"
	"strings"
)

// 1
// https://leetcode-cn.com/problems/two-sum/
func TwoSum1(nums []int, target int) []int {
	var result = make([]int, 0)
I:
	for ik, iv := range nums {
		for jk, jv := range nums[ik+1:] {
			if iv+jv == target {
				result = append(result, ik)
				result = append(result, ik+jk+1)
				break I
			}
		}
	}
	return result
}

func TwoSum2(nums []int, target int) []int {
	var tmp = make(map[int]int)
	for k, v := range nums {
		if i, ok := tmp[target-v]; ok {
			return []int{i, k}
		}
		tmp[v] = k
	}
	return []int{0, 0}
}

// 2
// https://leetcode-cn.com/problems/add-two-numbers/
func AddTwoNumbers1(l1, l2 *ListNode) *ListNode {
	var result = new(ListNode)
	if l1 != nil && l2 != nil {
		result.Val = l1.Val + l2.Val
		if l1.Next != nil || l2.Next != nil {
			result.Next = AddTwoNumbers1(l1.Next, l2.Next)
		}
	} else if l1 != nil && l2 == nil {
		result.Val = l1.Val
		if l1.Next != nil {
			result.Next = AddTwoNumbers1(l1.Next, nil)
		}
	} else if l1 == nil && l2 != nil {
		result.Val = l2.Val
		if l2.Next != nil {
			result.Next = AddTwoNumbers1(nil, l2.Next)
		}
	}
	if result.Val >= 10 {
		result.Val %= 10
		result.Next = AddTwoNumbers1(result.Next, &ListNode{1, nil})
	}
	return result
}

func AddTwoNumbers2(l1, l2 *ListNode) *ListNode {
	var result, ptr *ListNode
	var ptr1 = l1
	var ptr2 = l2
	for ptr1 != nil || ptr2 != nil {
		//移动指针
		if ptr == nil {
			ptr = &ListNode{0, nil}
			result = ptr
		} else {
			if ptr.Next == nil {
				ptr.Next = &ListNode{0, nil}
			}
			ptr = ptr.Next
		}
		//当前节点计算
		if ptr1 != nil {
			ptr.Val += ptr1.Val
			ptr1 = ptr1.Next
		} else {
			ptr1 = nil
		}
		if ptr2 != nil {
			ptr.Val += ptr2.Val
			ptr2 = ptr2.Next
		} else {
			ptr2 = nil
		}
		//处理进位
		if ptr.Val >= 10 {
			ptr.Val %= 10
			ptr.Next = &ListNode{1, nil}
		}
	}
	return result
}

// 3
// https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
func LengthOfLongestSubstring1(s string) int {
	var subStr = make(map[byte]int)
	var max = 0
	var start = 0
	for k, v := range []byte(s) {
		if index, ok := subStr[v]; ok && index >= start {
			start = index + 1
		}
		fmt.Println(k, v, start)
		if max < k-start+1 {
			max = k - start + 1
		}
		subStr[v] = k
	}
	return max
}

func LengthOfLongestSubstring2(s string) int {
	//fmt.Println(s)
	var chars = []rune(s)
	var start, count, max = 0, 0, 0
	var maps = make(map[rune]int)
	for k, v := range chars {
		count = 0
		index, ok := maps[v]
		if ok {
			if index-start > k-index {
				count = index - start
			} else {
				count = k - index
			}
			start = index + 1
			for sk, sv := range maps {
				if sv <= index {
					delete(maps, sk)
				}
			}
		} else {
			count = k - start + 1
		}
		maps[v] = k
		if max < count {
			max = count
		}
		//fmt.Println(start, index, k, v, count, max, maps)
	}
	return max
}

//最佳答案,抄的
func LengthOfLongestSubstring3(s string) int {
	var maps = make(map[rune]int)
	var start, max = 0, 0
	for k, v := range []rune(s) {
		if index, ok := maps[v]; ok && index >= start {
			start = index + 1
		}
		if k-start+1 > max {
			max = k - start + 1
		}
		maps[v] = k
		fmt.Println(k, v, start, maps)
	}
	return max
}

// 4
// https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
func FindMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	var m, n = len(nums1), len(nums2)
	if m > n {
		m, n, nums1, nums2 = n, m, nums2, nums1
	}
	var left, right, half = 0, m, (m + n + 1) / 2
	var odd = (m+n)%2 == 1
	var i, j = 0, 0
	for left <= right {
		i = (left + right) / 2
		j = half - i
		if i < right && nums2[j-1] > nums1[i] {
			left = i + 1
		} else if i > left && nums1[i-1] > nums2[j] {
			right = i - 1
		} else {
			var maxLeft = 0
			if i == 0 {
				maxLeft = nums2[j-1]
			} else if j == 0 {
				maxLeft = nums1[i-1]
			} else {
				maxLeft = nums1[i-1]
				if maxLeft < nums2[j-1] {
					maxLeft = nums2[j-1]
				}
			}

			if odd {
				return float64(maxLeft)
			}

			var minRight = 0
			if i == m {
				minRight = nums2[j]
			} else if j == n {
				minRight = nums1[i]
			} else {
				minRight = nums1[i]
				if minRight > nums2[j] {
					minRight = nums2[j]
				}
			}
			return float64(maxLeft+minRight) / 2.0
		}
	}
	return 0.0
}

// 5
// https://leetcode-cn.com/problems/longest-palindromic-substring/
func LongestPalindrome1(s string) string {
	if len(s) < 2 {
		return s
	}
	var sRunes = []rune(s)
	var indexes = map[rune][]int{}             //存储每个字符的所有地址
	var maxStr = []rune{sRunes[len(sRunes)-1]} //最大回文，默认最后一个字符
	for k, v := range sRunes {
		if _, ok := indexes[v]; ok {
			for _, index := range indexes[v] {
				if len(maxStr) > k-index+1 {
					break
				}
				var founded = true
				for kk, vv := range sRunes[index : k+1] {
					if vv != sRunes[index : k+1][len(sRunes[index:k+1])-1-kk] {
						founded = false
						break
					}
				}
				//找到就推出当前循环
				if founded {
					maxStr = sRunes[index : k+1]
					break
				}
			}
		}
		if indexes[v] == nil {
			indexes[v] = []int{k}
		} else {
			indexes[v] = append(indexes[v], k)
		}
	}
	return string(maxStr)
}

func LongestPalindrome2(s string) string {
	if len(s) < 2 {
		return s
	}
	var sRunes = []rune(s)
	var maxStr = []rune{sRunes[len(sRunes)-1]} //最大回文，默认最后一个字符
	var left, right int
	var len1, len2 int //奇数长、偶数长
	for k := range sRunes {
		len1, len2 = 0, 0
		left, right = k-1, k+1
		for left >= 0 && right < len(sRunes) {
			if sRunes[left] != sRunes[right] {
				break
			}
			len1 = right - left + 1
			left--
			right++
		}
		left, right = k, k+1
		for left >= 0 && right < len(sRunes) {
			if sRunes[left] != sRunes[right] {
				break
			}
			len2 = right - left + 1
			left--
			right++
		}
		if len(maxStr) <= len1 || len(maxStr) <= len2 {
			if len1 < len2 {
				len1 = len2
			}
			maxStr = sRunes[k-(len1-1)/2 : k+len1/2+1]
		}
	}
	return string(maxStr)
}

// 6
// https://leetcode-cn.com/problems/zigzag-conversion/
func Convert(s string, numRows int) string {
	if numRows < 2 {
		return s
	}
	var maps = make([]bytes.Buffer, numRows)
	for i := 0; i < len(s); i++ {
		var remain = i % (2*numRows - 2)
		if remain < numRows {
			maps[remain].WriteByte(s[i])
		} else {
			maps[numRows-(remain+1-numRows)-1].WriteByte(s[i])
		}
	}
	for i := 1; i < numRows; i++ {
		maps[0].Write(maps[i].Bytes())
	}

	return maps[0].String()
}

// 7
// https://leetcode-cn.com/problems/reverse-integer/
func ReverseInt1(x int) int {
	var result int64 = 0
	for x != 0 {
		result = result*10 + int64(x%10)
		x /= 10
	}
	if result > math.MaxInt32 || result < -math.MaxInt32 {
		return 0
	}
	return int(result)
}

// 8
// https://leetcode-cn.com/problems/string-to-integer-atoi/
func MyAtoi1(str string) int {
	var number int
	var negative = false
	var begin = false //已经开始解析到数字
	for len(str) > 0 && number <= math.MaxInt32 && number >= -math.MaxInt32-1 {
		if str[0] >= 48 && str[0] <= 57 {
			number = number*10 + int(str[0]-48)
			begin = true
		} else {
			if begin {
				break
			}
			if str[0] == 32 {
			} else if str[0] == 43 {
				negative = false
				begin = true
			} else if str[0] == 45 {
				negative = true
				begin = true
			} else {
				break
			}
		}
		str = str[1:]
	}
	if negative {
		number = -number
	}
	if number > math.MaxInt32 {
		return math.MaxInt32
	} else if number < -math.MaxInt32-1 {
		return -math.MaxInt32 - 1
	} else {
		return number
	}
}

// 9
// https://leetcode-cn.com/problems/palindrome-number/
func IsPalindrome1(x int) bool {
	if x < 0 || (x%10 == 0 && x != 0) {
		return false
	}
	var result = 0
	for x > result {
		result = result*10 + x%10
		x /= 10
	}
	return x == result || x == result/10
}

func IsPalindrome2(x int) bool {
	if x < 0 {
		return false
	} else if x < 10 {
		return true
	} else {
		var result = 0
		for x != 0 {
			result = result*10 + x%10
			if result == 0 {
				return false
			}
			x /= 10
			if x == result {
				return true
			} else if x < result {
				return result/10 == x
			}
		}
		return false
	}
}

// 10 TODO
// https://leetcode-cn.com/problems/regular-expression-matching/
func IsMatch(s string, p string) bool {
	if len(p) == 0 {
		return len(s) == 0
	}
	if len(s) == 0 {
		return len(p) == 0 || (len(p) == 2 && p[1] == '*')
	}
	var first_match = s[0] == p[0] || p[0] == '.'
	if len(p) > 1 && p[1] == '*' {
		return IsMatch(s, p[2:]) || (first_match && IsMatch(s[1:], p)) //匹配0次或者匹配1次，其他的交给递归
	} else {
		return first_match && IsMatch(s[1:], p[1:])
	}
}

// 11
// https://leetcode-cn.com/problems/container-with-most-water/
func MaxArea1(height []int) int {
	var left, right = 0, len(height) - 1
	var maxArea = 0
	for left < right {
		if height[left] < height[right] {
			if maxArea < height[left]*(right-left) {
				maxArea = height[left] * (right - left)
			}
			left++
		} else {
			if maxArea < height[right]*(right-left) {
				maxArea = height[right] * (right - left)
			}
			right--
		}
	}
	return maxArea
}

// 12
// https://leetcode-cn.com/problems/integer-to-roman/
func IntToRoman1(num int) string {
	var str string
	var i = 0
	var numMaps = map[int][2]string{
		0: {"I", "V"},
		1: {"X", "L"},
		2: {"C", "D"},
		3: {"M", ""},
	}
	var maps [2]string
	for num > 0 {
		maps = numMaps[i]
		switch num % 10 {
		case 1:
			str = maps[0] + str
		case 2:
			str = maps[0] + maps[0] + str
		case 3:
			str = maps[0] + maps[0] + maps[0] + str
		case 4:
			str = maps[0] + maps[1] + str
		case 5:
			str = maps[1] + str
		case 6:
			str = maps[1] + maps[0] + str
		case 7:
			str = maps[1] + maps[0] + maps[0] + str
		case 8:
			str = maps[1] + maps[0] + maps[0] + maps[0] + str
		case 9:
			if v, ok := numMaps[i+1]; ok {
				str = maps[0] + v[0] + str
			}
		}
		i++
		num /= 10
	}
	return str
}

func IntToRoman2(num int) string {
	var str string
	var roman = []string{"I", "V", "X", "L", "C", "D", "M"}
	var remain, index, i int
	for num > 0 {
		remain = num % 10
		if remain > 0 {
			i = remain % 5
			if i == 4 {
				str = roman[index] + roman[index+(remain+1)/5] + str
			} else {
				for i > 0 {
					str = roman[index] + str
					i--
				}
				if remain > 4 {
					str = roman[index+1] + str
				}
			}
		}
		//fmt.Println(str)
		index += 2
		num /= 10
	}
	return str
}

func IntToRoman3(num int) string {
	var str = [15]byte{} //最大15个字符
	var roman = [7]byte{73, 86, 88, 76, 67, 68, 77}
	var result, i, last, index, divisor = 0, 0, 0, 6, 1000
	for num > 0 {
		result = num / divisor
		if result > 0 {
			i = result % 5
			if i == 4 {
				str[last] = roman[index]
				last++
				str[last] = roman[index+(result+1)/5]
				last++
			} else {
				if result > 4 {
					str[last] = roman[index+1]
					last++
				}
				for i > 0 {
					str[last] = roman[index]
					last++
					i--
				}
			}
		}
		index -= 2
		num %= divisor
		divisor /= 10
	}
	return string(str[:last])
}

// 13
// https://leetcode-cn.com/problems/roman-to-integer/
func RomanToInt1(s string) int {
	var roman = map[byte]int{'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
	var num = 0
	var last byte = 0
	for _, v := range []byte(s) {
		if last != 0 && roman[v] > roman[last] {
			num -= roman[last] * 2
		}
		num += roman[v]
		last = v
	}
	return num
}

func RomanToInt2(s string) int {
	var roman = map[byte]int{'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
	var num, ptr = 0, 0
	var left, right int
	for ptr < len(s) {
		left, right = roman[s[ptr]], 0
		if ptr+1 < len(s) {
			right = roman[s[ptr+1]]
		}
		if left >= right {
			num += roman[s[ptr]]
			ptr++
			continue
		}

		num += right - left
		ptr += 2
	}
	return num
}

// 14
// https://leetcode-cn.com/problems/longest-common-prefix/
func LongestCommonPrefix(strs []string) string {
	if len(strs) == 0 || len(strs[0]) == 0 {
		return ""
	}
	var str bytes.Buffer
begin:
	for i := 0; i < len(strs[0]); i++ {
		s := strs[0][i]
		for _, v := range strs[1:] {
			//fmt.Println(v, string(v[i]))
			if i >= len(v) {
				break begin
			}
			if v[i] != s {
				break begin
			}
		}
		str.WriteByte(s)
		//fmt.Println(str.String())
	}
	return str.String()
}

// 15
// https://leetcode-cn.com/problems/3sum/
func ThreeSum1(nums []int) [][]int {
	var res = make([][]int, 0)
	if len(nums) >= 3 {
		sort.Ints(nums)
		//fmt.Println(nums)
		var last = nums[0] - 1
		var k, low, high = 0, 0, 0
		for i := 0; i < len(nums); i++ {
			//fmt.Println(nums[i])
			if nums[i] > 0 {
				break
			}
			if nums[i] == last {
				continue
			}
			//fmt.Println("iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii")
			for j := len(nums) - 1; j > i; j-- {
				//fmt.Println(nums[i], nums[j])
				if nums[i]+nums[j] < -nums[j] {
					break
				}
				if nums[j] == last {
					continue
				}
				//fmt.Println("jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj")
				low, high = i+1, j-1
				for low <= high {
					k = (low + high) / 2
					//fmt.Println(i, j, k, low, high, nums[i], nums[j], nums[k])
					if nums[i]+nums[j]+nums[k] == 0 {
						res = append(res, []int{nums[i], nums[k], nums[j]})
						break
					} else if nums[i]+nums[j]+nums[k] > 0 {
						high = k - 1
					} else {
						low = k + 1
					}
				}
				last = nums[j]
			}
			last = nums[i]
		}
		//fmt.Println(res, tmp)
	}
	return res
}

func ThreeSum2(nums []int) [][]int {
	var res = make([][]int, 0)
	if len(nums) >= 3 {
		sort.Ints(nums)
		//fmt.Println(nums)
		var mid, right, midTmp int
		for left := 0; left < len(nums)-2 && nums[left] < 1; left++ {
			if left > 0 && nums[left] == nums[left-1] {
				continue
			}
			mid, right, midTmp = left+1, len(nums)-1, nums[0]-1
			for mid < len(nums)-1 && mid < right {
				if nums[left]+nums[mid]+nums[right] == 0 {
					//fmt.Println(left, mid, right, nums[left], nums[mid], nums[right], midTmp)
					if midTmp != nums[mid] {
						res = append(res, []int{nums[left], nums[mid], nums[right]})
						midTmp = nums[mid]
						right--
					}
					mid++
				} else if nums[left]+nums[mid]+nums[right] > 0 {
					if nums[mid]*2+nums[left] > 0 {
						break
					}
					right--
				} else {
					if nums[right] < 0 {
						break
					}
					mid++
				}
			}
		}
	}
	return res
}

// 16
// https://leetcode-cn.com/problems/3sum-closest/
func ThreeSumClosest1(nums []int, target int) int {
	if len(nums) < 3 {
		return 0
	}
	var sum = nums[0] + nums[1] + nums[2]
	var tmp int
	var abs = func(i int) int {
		if i >= 0 {
			return i
		} else {
			return -i
		}
	}
I:
	for i := 0; i < len(nums); i++ {
		for j := len(nums) - 1; j > i; j-- {
			for k := i + 1; k < j; k++ {
				tmp = nums[i] + nums[j] + nums[k]
				if abs(target-tmp) < abs(target-sum) {
					sum = tmp
				}
				if sum == target {
					break I
				}
			}
		}
	}

	return sum
}

func ThreeSumClosest2(nums []int, target int) int {
	if len(nums) < 3 {
		return 0
	}
	sort.Ints(nums)
	var mid, right, tmp int
	var sum = nums[0] + nums[1] + nums[2]
	for left := 0; left < len(nums); left++ {
		mid, right = left+1, len(nums)-1
		for mid < right {
			tmp = nums[left] + nums[mid] + nums[right]
			if tmp == target {
				return tmp
			} else if tmp < target {
				if sum < tmp || (sum > target && sum-target > target-tmp) {
					sum = tmp
				}
				mid++
			} else {
				if sum > tmp || (sum < target && target-sum > tmp-target) {
					sum = tmp
				}
				right--
			}
		}
	}
	return sum
}

// 17
// https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
func LetterCombinations(digits string) []string {
	if len(digits) == 0 {
		return []string{}
	}
	dm := map[byte][]byte{
		'2': {'a', 'b', 'c'},
		'3': {'d', 'e', 'f'},
		'4': {'g', 'h', 'i'},
		'5': {'j', 'k', 'l'},
		'6': {'m', 'n', 'o'},
		'7': {'p', 'q', 'r', 's'},
		'8': {'t', 'u', 'v'},
		'9': {'w', 'x', 'y', 'z'},
	}
	var res []string
	var dfs func(s string)
	dfs = func(s string) {
		if len(s) == len(digits) {
			res = append(res, s)
		} else {
			if v, ok := dm[digits[len(s)]]; ok {
				for _, b := range v {
					dfs(s + string(b))
				}
			}
		}
	}
	dfs(``)
	return res
}

// 18
// https://leetcode-cn.com/problems/4sum/
func FourSum1(nums []int, target int) [][]int {
	var res = make([][]int, 0)
	if len(nums) >= 4 {
		sort.Ints(nums)
		//fmt.Println(nums)
		var left, right, leftTmp int
		for start := 0; start < len(nums)-3 && nums[start] < target/4+1; start++ {
			if start > 0 && nums[start] == nums[start-1] {
				continue
			}
			for end := len(nums) - 1; end > start+2 && nums[end] > target/4-1; end-- {
				if end < len(nums)-1 && nums[end] == nums[end+1] {
					continue
				}
				left, right, leftTmp = start+1, end-1, nums[0]-1
				for left < right {
					//fmt.Println(start, left, right, end, leftTmp)
					if nums[start]+nums[left]+nums[right]+nums[end] == target {
						if leftTmp != nums[left] {
							res = append(res, []int{nums[start], nums[left], nums[right], nums[end]})
							leftTmp = nums[left]
							right--
						}
						left++
					} else if nums[start]+nums[left]+nums[right]+nums[end] > target {
						right--
					} else {
						left++
					}
				}
			}
		}
	}
	return res
}

// RemoveNthFromEnd
// 19
// https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
func RemoveNthFromEnd(head *ListNode, n int) *ListNode {
	head = &ListNode{Val: 0, Next: head}
	s, f := head, head

	for n > 0 && f.Next != nil {
		f = f.Next
		n--
	}

	for f.Next != nil {
		s, f = s.Next, f.Next
	}

	s.Next = s.Next.Next

	return head.Next
}

// 20
// https://leetcode-cn.com/problems/valid-parentheses/
func IsValid(s string) bool {
	var leftBrackets = map[byte]byte{'{': '}', '[': ']', '(': ')'}
	var rightBrackets = map[byte]byte{'}': '{', ']': '[', ')': '('}
	var finds = make([]byte, 0)
	for i := 0; i < len(s); i++ {
		if _, ok := leftBrackets[s[i]]; ok {
			finds = append(finds, leftBrackets[s[i]])
			continue
		}
		if _, ok := rightBrackets[s[i]]; ok {
			if len(finds) == 0 || finds[len(finds)-1] != s[i] {
				return false
			}
			finds = finds[:len(finds)-1]
		}
	}
	return len(finds) == 0
}

// MergeTwoLists
// 21
// https://leetcode-cn.com/problems/merge-two-sorted-lists/
func MergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	if l2 == nil {
		return l1
	}
	if l1 == nil {
		return l2
	}
	if l1.Val > l2.Val {
		l1, l2 = l2, l1
	}

	ptr := l1
	for l1.Next != nil && l2 != nil {
		if l1.Next.Val > l2.Val {
			l1.Next, l2.Next, l2 = l2, l1.Next, l2.Next
		}
		l1 = l1.Next
	}
	if l2 != nil {
		l1.Next = l2
	}

	return ptr
}

// 22 TODO
// https://leetcode-cn.com/problems/generate-parentheses/
func GenerateParenthesis(n int) []string {
	var parenthesis []string
	var order func(str string, l, r, n int)
	order = func(str string, l, r, n int) {
		if l > n || r > n || r > l {
			return
		}
		if l == n && r == n {
			parenthesis = append(parenthesis, str)
		}
		order(str+`(`, l+1, r, n)
		order(str+`)`, l, r+1, n)
	}
	order(``, 0, 0, n)
	return parenthesis
}

// 23
// https://leetcode-cn.com/problems/merge-k-sorted-lists/
func MergeKLists(lists []*ListNode) *ListNode {
	if len(lists) == 0 {
		return nil
	}
	var mergeLists func(l1, l2 *ListNode) *ListNode
	var splitLists func(lists []*ListNode) []*ListNode
	mergeLists = func(l1, l2 *ListNode) *ListNode {
		if l1 == nil {
			return l2
		} else if l2 == nil {
			return l1
		}
		if l1.Val > l2.Val {
			l1, l2 = l2, l1
		}
		var p = l1
		for l1 != nil {
			if l1.Next == nil {
				l1.Next = l2
				break
			}
			if l1.Next.Val > l2.Val {
				l1.Next, l2 = l2, l1.Next
			}
			l1 = l1.Next
		}
		return p
	}
	splitLists = func(lists []*ListNode) []*ListNode {
		var newLists []*ListNode
		for i := 0; i <= len(lists)-2; i += 2 {
			newLists = append(newLists, mergeLists(lists[i], lists[i+1]))
		}
		if len(lists)%2 == 1 {
			newLists = append(newLists, lists[len(lists)-1])
		}
		return newLists
	}
	for len(lists) > 1 {
		lists = splitLists(lists)
	}
	return lists[0]
}

// 24
// https://leetcode-cn.com/problems/swap-nodes-in-pairs/
func SwapPairs(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	var ptr = head
	var last *ListNode
	head = head.Next
	for ptr != nil && ptr.Next != nil {
		ptr, ptr.Next, ptr.Next.Next = ptr.Next, ptr.Next.Next, ptr
		if last != nil {
			last.Next = ptr
		}
		last = ptr.Next
		ptr = ptr.Next.Next
	}
	return head
}

// 25
// https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
func ReverseKGroup(head *ListNode, k int) *ListNode {
	var p, q *ListNode
	for head != nil {
		var index, list = k, make([]*ListNode, k)
		for i := k - 1; i >= 0 && head != nil; i-- {
			index, head, list[i] = i, head.Next, head
			if i < k-1 {
				list[i].Next = list[i+1]
			} else {
				list[i].Next = nil
			}
		}
		if index == k {
			break
		}
		if index > 0 {
			var newList = make([]*ListNode, k-index)
			for i := k - 1; i >= index; i-- {
				newList[k-1-i] = list[i]
				if k-1-i > 0 {
					newList[k-1-i-1].Next = newList[k-1-i]
				}
			}
			index = 0
			list = newList
			list[len(list)-1].Next = nil
		}
		if p == nil {
			p = list[index]
		}
		if q != nil {
			q.Next = list[index]
		}
		q = list[len(list)-1]
	}
	return p
}

// 26
// https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
func RemoveDuplicates(nums []int) int {
	var length, index = 0, 0
	for k, v := range nums {
		//fmt.Println(k, v)
		if k == 0 {
			length++
		} else if v > nums[index] {
			nums[index+1], nums[k] = nums[k], nums[index+1]
			index++
			length++
		}
	}
	//fmt.Println(nums)
	return length
}

// 27
// https://leetcode-cn.com/problems/remove-element/
func RemoveElement(nums []int, val int) int {
	var index = 0
	for k, v := range nums {
		if val != v {
			nums[index], nums[k] = nums[k], nums[index]
			index++
		}
	}
	return index
}

// 28
// https://leetcode-cn.com/problems/implement-strstr/
func StrStr(haystack string, needle string) int {
	m, n := len(haystack), len(needle)
	if n == 0 {
		return 0
	}
	if m < n {
		return -1
	}
	for i := 0; i <= m-n; i++ {
		if haystack[i] == needle[0] && haystack[i:i+n] == needle {
			return i
		}
	}
	return -1
}

// 29
// https://leetcode-cn.com/problems/divide-two-integers/
func Divide(dividend int, divisor int) int {
	if dividend == 0 {
		return 0
	}
	var negative = dividend < 0
	if dividend < 0 {
		dividend = -dividend
	}
	if divisor < 0 {
		divisor = -divisor
		negative = !negative
	}
	var total, i = 0, 0
	if divisor == 1 {
		i = dividend
	} else {
		for total <= dividend-divisor {
			total += divisor + divisor
			i += 2
		}
	}
	if i*divisor > dividend {
		i--
	}
	if negative {
		return -i
	}
	if i > math.MaxInt32 {
		i = math.MaxInt32
	}
	return i
}

// 30

// 31
// https://leetcode-cn.com/problems/next-permutation/
func NextPermutation(nums []int) {
	for i := len(nums) - 1; i >= 0; i-- {
		for j := i + 1; j < len(nums); j++ {
			if nums[j] > nums[i] {
				nums[i], nums[j] = nums[j], nums[i]
				return
			}
		}
		var index = i
		for j := i + 1; j < len(nums); j++ {
			if nums[index] > nums[j] {
				nums[index], nums[j] = nums[j], nums[index]
				index++
			}
		}
	}
}

// 32
// https://leetcode-cn.com/problems/longest-valid-parentheses/

// 33
// https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
func Search(nums []int, target int) int {
	var index = -1
	var left, right = 0, len(nums) - 1
	for left <= right {
		var middle = (left + right) / 2
		if nums[middle] == target {
			index = middle
			break
		} else if target < nums[left] && nums[middle] >= nums[left] {
			left = middle + 1
		} else if target >= nums[left] && nums[middle] < nums[left] {
			right = middle - 1
		} else {
			if nums[middle] < target {
				left = middle + 1
			} else {
				right = middle - 1
			}
		}
	}
	return index
}

// 34
// https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
func SearchRange(nums []int, target int) []int {
	var left, right = 0, len(nums) - 1
	var index = -1
	for left <= right {
		var middle = (left + right) / 2
		if nums[middle] == target {
			index = middle
			break
		} else if nums[middle] < target {
			left = middle + 1
		} else {
			right = middle - 1
		}
	}
	if index == -1 {
		return []int{-1, -1}
	}
	var start, end = index, index
	left, right = 0, len(nums)-1
	for left <= start {
		var middle = (left + start) / 2
		if nums[middle] < target || start == middle {
			left = middle + 1
		} else {
			start = middle
		}
	}
	for end <= right {
		var middle = (end + right + 1) / 2
		if nums[middle] > target || end == middle {
			right = middle - 1
		} else {
			end = middle
		}
	}
	return []int{start, end}
}

// 35
// https://leetcode-cn.com/problems/search-insert-position/
func SearchInsert1(nums []int, target int) int {
	l, r := 0, len(nums)-1
	var m int
	for l < r {
		m = (l + r) / 2
		if nums[m] == target {
			return m
		}

		if nums[m] < target {
			l = m + 1
		} else {
			r = m
		}
	}
	if l == r && target > nums[l] {
		l++
	}
	return l
}

func SearchInsert2(nums []int, target int) int {
	var left, right = 0, len(nums) - 1
	for left < right {
		m := (right-left)/2 + left
		if nums[m] == target {
			return m
		} else if nums[m] > target {
			right = m
		} else {
			left = m + 1
		}
	}
	return right
}

// 36
// https://leetcode-cn.com/problems/valid-sudoku/
func IsValidSudoKu(board [][]byte) bool {
	var cols = make([]map[byte]bool, 9)
	var cells = make([]map[byte]bool, 9)
	for i := 0; i < 9; i++ {
		var rows = make(map[byte]bool)
		for j := 0; j < 9; j++ {
			if board[i][j] == 46 {
				continue
			}
			var cell = i/3 + j/3*3
			if _, ok := rows[board[i][j]]; ok {
				return false
			}
			if _, ok := cols[j][board[i][j]]; ok {
				return false
			}
			if _, ok := cells[cell][board[i][j]]; ok {
				return false
			}
			if cols[j] == nil {
				cols[j] = make(map[byte]bool)
			}
			if cells[cell] == nil {
				cells[cell] = make(map[byte]bool)
			}
			rows[board[i][j]] = true
			cols[j][board[i][j]] = true
			cells[cell][board[i][j]] = true
		}
	}
	return true
}

// 37

// 38
// https://leetcode-cn.com/problems/count-and-say/
func CountAndSay(n int) string {
	var str = bytes.Buffer{}
	str.WriteString("1")
	for i := 2; i <= n; i++ {
		var num, count = str.Bytes()[0], 0
		var tmp = bytes.Buffer{}
		for _, v := range str.Bytes() {
			if num == v {
				count++
			} else {
				tmp.WriteString(strconv.Itoa(count))
				tmp.WriteByte(num)
				num, count = v, 1
			}
		}
		str = tmp
		str.WriteString(strconv.Itoa(count))
		str.WriteByte(num)
	}
	return str.String()
}

// 39
// https://leetcode-cn.com/problems/combination-sum/
func CombinationSum(candidates []int, target int) [][]int {
	var res [][]int
	var backtrace func(index, total int, arr []int)
	backtrace = func(index, total int, arr []int) {
		if total == target {
			res = append(res, make([]int, len(arr)))
			copy(res[len(res)-1], arr)
		} else if total < target {
			for i := index; i < len(candidates); i++ {
				backtrace(i, total+candidates[i], append(arr, candidates[i]))
			}
		}
	}
	backtrace(0, 0, []int{})
	return res
}

// 40
// https://leetcode-cn.com/problems/combination-sum-ii/
func CombinationSum2(candidates []int, target int) [][]int {
	sort.Ints(candidates)
	var res [][]int
	var backtrace func(index, total int, arr []int)
	backtrace = func(index, total int, arr []int) {
		if total == target {
			res = append(res, make([]int, len(arr)))
			copy(res[len(res)-1], arr)
		} else if total < target {
			for i := index; i < len(candidates); i++ {
				if i > index && candidates[i] == candidates[i-1] {
					continue
				}
				backtrace(i+1, total+candidates[i], append(arr, candidates[i]))
			}
		}
	}
	backtrace(0, 0, []int{})
	return res
}

// 41
// https://leetcode-cn.com/problems/first-missing-positive/
func FirstMissingPositive(nums []int) int {
	var exists = make(map[int]bool)
	var min = 1
	for _, v := range nums {
		if v > 0 {
			exists[v] = true
			for {
				if _, ok := exists[min]; ok {
					min++
				} else {
					break
				}
			}
		}
	}
	return min
}

// 42
// https://leetcode-cn.com/problems/trapping-rain-water/
func Trap(height []int) int {
	var left, right = 0, len(height) - 1
	var area, level = 0, 0
	for left < right {
		if height[left] <= level {
			area += level - height[left]
			left++
		} else if height[right] <= level {
			area += level - height[right]
			right--
		} else {
			if height[left] <= height[right] {
				level = height[left]
				left++
			} else {
				level = height[right]
				right--
			}
		}
	}
	return area
}

// 43
// https://leetcode-cn.com/problems/multiply-strings/

// 44

// 45
// https://leetcode-cn.com/problems/jump-game-ii/
func Jump(nums []int) int {
	//var arr1 = []int{3, 4, 3, 1, 0, 7, 0, 3, 0, 2, 0, 3}
	//var arr1 = []int{7, 0, 9, 6, 9, 6, 1, 7, 9, 0, 1, 2, 9, 0, 3}
	var step, index, length = 0, 0, len(nums)
	for index < length-1 {
		if nums[index]+index >= length-1 {
			step++
			break
		}
		var maxIndex, maxValue = index + 1, 0
		for i := index + 1; i <= index+nums[index] && i < length; i++ {
			if maxValue <= nums[i]+i {
				maxValue = nums[i] + i
				maxIndex = i
			}
		}
		step++
		index = maxIndex
	}
	return step
}

// 46
// https://leetcode-cn.com/problems/permutations/
func Permute(nums []int) [][]int {
	res := make([][]int, 0)
	n := len(nums)
	var backtrace func(index int, arr []int)
	backtrace = func(index int, arr []int) {
		if index == n {
			res = append(res, make([]int, n))
			copy(res[len(res)-1], arr)
		}
		for i := index; i < n; i++ {
			arr[index], arr[i] = arr[i], arr[index]
			backtrace(index+1, arr)
			arr[index], arr[i] = arr[i], arr[index]
		}
	}
	backtrace(0, nums)
	return res
}

// 47
// https://leetcode-cn.com/problems/permutations-ii
func PermuteUnique(nums []int) [][]int {
	res := make([][]int, 0)
	n := len(nums)
	var backtrace func(index int, arr []int)
	backtrace = func(index int, arr []int) {
		if index == n {
			res = append(res, make([]int, n))
			copy(res[len(res)-1], arr)
		}
		m := make(map[int]bool)
		for i := index; i < n; i++ {
			if _, ok := m[arr[i]]; ok {
				continue
			}
			arr[index], arr[i] = arr[i], arr[index]
			backtrace(index+1, arr)
			arr[index], arr[i] = arr[i], arr[index]
			m[arr[i]] = true
		}
	}
	backtrace(0, nums)
	return res
}

// 48
// https://leetcode-cn.com/problems/rotate-image
func Rotate2(matrix [][]int) {
	rot := func(x, y, l int) {
		for i := 0; i < l-1; i++ {
			matrix[x][y+i], matrix[x+i][y+l-1], matrix[x+l-1][y+l-1-i], matrix[x+l-1-i][y] = matrix[x+l-1-i][y], matrix[x][y+i], matrix[x+i][y+l-1], matrix[x+l-1][y+l-1-i]
		}
	}
	for i := 0; i < len(matrix)/2; i++ {
		rot(i, i, len(matrix)-i*2)
	}
}

// 49
// https://leetcode-cn.com/problems/group-anagrams
func GroupAnagrams(strs []string) [][]string {
	m := make(map[string][]string)
	for _, str := range strs {
		key := make([]byte, 26)
		for i := 0; i < len(str); i++ {
			key[int(str[i]-'a')]++
		}
		if _, ok := m[string(key)]; !ok {
			m[string(key)] = make([]string, 0)
		}
		m[string(key)] = append(m[string(key)], str)
	}
	res := make([][]string, 0)
	for _, v := range m {
		res = append(res, v)
	}
	return res
}

// 50
// https://leetcode-cn.com/problems/powx-n/
func MyPow(x float64, n int) float64 {
	var res = 1.0
	for i := n; i != 0; i /= 2 {
		if i%2 != 0 {
			res *= x
		}
		x *= x
	}
	if n < 0 {
		res = 1 / res
	}
	return res
}

// 51

// 52

// 53
// https://leetcode-cn.com/problems/maximum-subarray/
func MaxSubArray(nums []int) int {
	var max, tmp = nums[0], 0
	for _, v := range nums {
		tmp += v
		if max < tmp {
			max = tmp
		}
		if tmp < 0 {
			tmp = 0
		}
	}
	return max
}

// 54
// https://leetcode-cn.com/problems/spiral-matrix/
func SpiralOrder(matrix [][]int) []int {
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return nil
	}
	var res []int
	var width, height = len(matrix[0]), len(matrix)
	var x, y, layer, direction = 0, 0, 0, 'r'
	for x >= layer && x <= height-1-layer && y >= layer && y <= width-1-layer {
		res = append(res, matrix[x][y])
		switch direction {
		case 'u':
			if x > layer+1 {
				x--
			} else {
				layer++
				y++
				direction = 'r'
			}
		case 'd':
			if x < height-1-layer {
				x++
			} else {
				y--
				direction = 'l'
			}
		case 'l':
			if y > layer {
				y--
			} else {
				x--
				direction = 'u'
				if x == layer {
					layer++
				}
			}
		case 'r':
			if y < width-1-layer {
				y++
			} else {
				x++
				direction = 'd'
			}
		}
	}
	return res
}

// 55
// https://leetcode-cn.com/problems/jump-game/
func CanJump(nums []int) bool {
	var index, length = 0, len(nums)
	for index < length-1 && nums[index]+index < length-1 {
		if nums[index] == 0 {
			return false
		}
		var maxIndex, maxValue = index + 1, 0
		for i := index + 1; i <= index+nums[index] && i < length; i++ {
			if maxValue <= nums[i]+i {
				maxValue = nums[i] + i
				maxIndex = i
			}
		}
		if maxValue+maxIndex == 0 && maxValue+maxIndex == index+nums[index] {
			return false
		}
		index = maxIndex
	}
	return true
}

// 56
// https://leetcode-cn.com/problems/merge-intervals/
func MergeSlice(intervals [][]int) [][]int {
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})
	var res [][]int
	for _, v := range intervals {
		if len(res) > 0 && res[len(res)-1][1] >= v[0] {
			if res[len(res)-1][1] < v[1] {
				res[len(res)-1][1] = v[1]
			}
		} else {
			res = append(res, v)
		}
	}
	return res
}

// 57
// https://leetcode-cn.com/problems/insert-interval/
func Insert(intervals [][]int, newInterval []int) [][]int {
	intervals = append(intervals, newInterval)
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})
	var res [][]int
	for _, v := range intervals {
		if len(res) > 0 && res[len(res)-1][1] >= v[0] {
			if res[len(res)-1][1] < v[1] {
				res[len(res)-1][1] = v[1]
			}
		} else {
			res = append(res, v)
		}
	}
	return res
}

// 58
// https://leetcode-cn.com/problems/length-of-last-word/
func LengthOfLastWord(s string) int {
	s = strings.TrimSpace(s)
	for i := len(s) - 1; i >= 0; i-- {
		if s[i] == ' ' {
			return len(s) - (i + 1)
		}
	}
	return len(s)
}

// 59
// https://leetcode-cn.com/problems/spiral-matrix-ii/
func GenerateMatrix(n int) [][]int {
	res := make([][]int, n)
	for i := 0; i < n; i++ {
		res[i] = make([]int, n)
	}
	x, y, dx, dy := 0, 0, 0, 1
	for i := 1; i <= n*n; i++ {
		res[x][y] = i
		if x+dx < 0 || x+dx >= n || y+dy < 0 || y+dy >= n || res[x+dx][y+dy] != 0 {
			dx, dy = dy, -dx
		}
		x, y = x+dx, y+dy
	}
	return res
}

// 60
// https://leetcode-cn.com/problems/permutation-sequence/
func GetPermutation(n int, k int) string {
	// 每个长度有多少个排列、数字
	counts, nums := make(map[int]int), make([]byte, 0)
	res := make([]byte, 0)
	for i := 1; i <= n; i++ {
		if i == 1 {
			counts[i] = 1
		} else {
			counts[i] = counts[i-1] * i
		}
		nums = append(nums, byte(n-i+1+'0'))
	}
	// counts[i]/k > 9 表示k值太小，此数位上没有数字可以选择
	for i := n; i >= 1 && counts[i]/k > 9; i-- {
		res = append(res, nums[i-1])
		delete(counts, i)
	}
	nums = nums[:len(counts)]               // 剩余未处理的数字
	length, count, key := len(counts), 0, 0 // 长度、不包括当前位数，排列个数、nums中的索引
	for length > 0 {
		count = counts[length] / length
		// 能整除，将第一个数字取出来，剩下的追加在后面
		if k%count == 0 {
			key = length - k/count
			res = append(res, nums[key])
			copy(nums[key:], nums[key+1:])
			res = append(res, nums[:length-1]...)
			break
		}
		//
		key = length - 1 - k/count
		k = k % (counts[length] / length)
		res = append(res, nums[key])
		copy(nums[key:], nums[key+1:])

		delete(counts, length)
		length = length - 1
	}
	//fmt.Println(string(res), nums)
	return string(res)
}

// 61
// https://leetcode-cn.com/problems/rotate-list/
func RotateRight(head *ListNode, k int) *ListNode {
	if k == 0 || head == nil {
		return head
	}
	var newHead, ptr = head, head
	var length = 1
	for ptr.Next != nil {
		ptr, length = ptr.Next, length+1
	}
	k, ptr.Next = k%length, head
	for i := 0; i < length-k; i++ {
		ptr = ptr.Next
	}
	newHead, ptr.Next = ptr.Next, nil
	return newHead
}

// 62
// https://leetcode-cn.com/problems/unique-paths/
func UniquePaths(m int, n int) int {
	var nums = make(map[string]int)
	var paths func(m, n int) int
	paths = func(m, n int) int {
		if m <= 1 || n <= 1 {
			return 1
		}
		var key = fmt.Sprintf(`%d-%d`, m, n)
		if _, ok := nums[key]; !ok {
			nums[key] = paths(m, n-1) + paths(m-1, n)
		}
		return nums[key]
	}
	return paths(m, n)
}

// 63
// https://leetcode-cn.com/problems/unique-paths-ii/
func UniquePathsWithObstacles(obstacleGrid [][]int) int {
	var m, n = len(obstacleGrid), len(obstacleGrid[0])
	if len(obstacleGrid) == 0 || len(obstacleGrid[0]) == 0 || obstacleGrid[m-1][n-1] == 1 {
		return 0
	}
	for i := m - 1; i >= 0; i-- {
		for j := n - 1; j >= 0; j-- {
			if obstacleGrid[i][j] == 1 {
				obstacleGrid[i][j] = 0
			} else {
				if i == m-1 && j == n-1 {
					obstacleGrid[i][j] = 1
				} else {
					if j < n-1 {
						obstacleGrid[i][j] += obstacleGrid[i][j+1]
					}
					if i < m-1 {
						obstacleGrid[i][j] += obstacleGrid[i+1][j]
					}
				}
			}
		}
	}
	return obstacleGrid[0][0]
}

// 64
// https://leetcode-cn.com/problems/minimum-path-sum/
func MinPathSum(grid [][]int) int {
	var m, n = len(grid), len(grid[0])
	for i := m - 1; i >= 0; i-- {
		for j := n - 1; j >= 0; j-- {
			if i != m-1 || j != n-1 {
				if i == m-1 {
					grid[i][j] += grid[i][j+1]
				} else if j == n-1 {
					grid[i][j] += grid[i+1][j]
				} else if grid[i][j+1] < grid[i+1][j] {
					grid[i][j] += grid[i][j+1]
				} else {
					grid[i][j] += grid[i+1][j]
				}
			}
		}
	}
	return grid[0][0]
}

// 65

// 66
// https://leetcode-cn.com/problems/plus-one/description/
func PlusOne(digits []int) []int {
	for i := len(digits) - 1; i >= 0; i-- {
		if digits[i] == 9 {
			digits[i] = 0
			if i == 0 {
				digits = append([]int{1}, digits...)
			}
		} else {
			digits[i] += 1
			break
		}
	}
	return digits
}

// 67
// https://leetcode-cn.com/problems/add-binary/
func AddBinary(a string, b string) string {
	if len(a) < len(b) {
		a, b = b, a
	}
	var last = 0
	var str = []rune(a)
	for i := 0; i < len(a); i++ {
		var tmp = 0
		if a[len(a)-(i+1)] == '1' {
			tmp++
		}
		if len(b)-(i+1) >= 0 && b[len(b)-(i+1)] == '1' {
			tmp++
		}
		if last == 1 {
			tmp++
		}
		if tmp == 1 || tmp == 3 {
			str[len(a)-(i+1)] = '1'
		} else {
			str[len(a)-(i+1)] = '0'
		}
		last = tmp / 2
		if i >= len(b)-1 && last == 0 {
			break
		}
	}
	if last > 0 {
		str = append([]rune{'1'}, str...)
	}
	return string(str)
}

// 68
//

// 69
// https://leetcode-cn.com/problems/sqrtx/
func MySQrt(x int) int {
	var left, right = 0, x/2 + 1
	for left < right {
		var middle = left + (right-left+1)/2
		if middle*middle > x {
			right = middle - 1
		} else {
			left = middle
		}
	}
	return left
}

// 70
// https://leetcode-cn.com/problems/climbing-stairs/
func ClimbStairs(n int) int {
	var a, b = 0, 1
	for i := 1; i <= n; i++ {
		a, b = b, a+b
	}
	return b
}

// 71
// https://leetcode-cn.com/problems/simplify-path/
func SimplifyPath(path string) string {
	var dst []string
	for _, v := range strings.Split(path, `/`) {
		if v == `` || v == `.` {
			continue
		}
		if v == `..` {
			if len(dst) > 0 {
				dst = dst[:len(dst)-1]
			}
		} else {
			dst = append(dst, v)
		}
	}
	return `/` + strings.Join(dst, `/`)
}

// 72
//

// 73
// https://leetcode-cn.com/problems/set-matrix-zeroes/
func SetZeroes(matrix [][]int) {
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return
	}
	var m, n = make([]uint64, len(matrix)/64+1), make([]uint64, len(matrix[0])/64+1)
	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[0]); j++ {
			if matrix[i][j] == 0 {
				m[i/64], n[j/64] = m[i/64]|1<<uint(i%64), n[j/64]|1<<uint(j%64)
			}
		}
	}
	for i := 0; i < len(matrix); i++ {
		if 1<<uint(i%64)&m[i/64] > 0 {
			for j := 0; j < len(matrix[0]); j++ {
				matrix[i][j] = 0
			}
		}
	}
	for j := 0; j < len(matrix[0]); j++ {
		if 1<<uint(j%64)&n[j/64] > 0 {
			for i := 0; i < len(matrix); i++ {
				matrix[i][j] = 0
			}
		}
	}
}

// 74
// https://leetcode-cn.com/problems/search-a-2d-matrix/
func SearchMatrix(matrix [][]int, target int) bool {
	xl, xh := 0, len(matrix)-1
	for xl <= xh {
		xm := (xl + xh) / 2
		if matrix[xm][len(matrix[0])-1] < target {
			xl = xm + 1
		} else if matrix[xm][0] > target {
			xh = xm - 1
		} else {
			yl, yr := 0, len(matrix[0])-1
			for yl <= yr {
				ym := (yl + yr) / 2
				if matrix[xm][ym] == target {
					return true
				}
				if matrix[xm][ym] < target {
					yl = ym + 1
				} else {
					yr = ym - 1
				}
			}
			return false
		}
	}
	return false
}

// 75
// https://leetcode-cn.com/problems/sort-colors/
func SortColors(nums []int) {
	l, r, index := -1, len(nums), 0
	for index < r {
		switch nums[index] {
		case 0:
			nums[l+1], nums[index] = nums[index], nums[l+1]
			l++
			if l == index {
				index++
			}
		case 1:
			index++
		case 2:
			nums[r-1], nums[index] = nums[index], nums[r-1]
			r--
		}
	}
}

// 76
//

// 77
// https://leetcode-cn.com/problems/combinations
func Combine(n int, k int) [][]int {
	var res [][]int
	var backtrace func(num int, arr []int)
	backtrace = func(num int, arr []int) {
		if len(arr) == k {
			res = append(res, append([]int{}, arr...))
		} else {
			for i := num; i <= n-(k-len(arr))+1; i++ {
				backtrace(i+1, append(arr, i))
			}
		}
	}
	backtrace(1, []int{})
	return res
}

// 78
// https://leetcode-cn.com/problems/subsets/
func Subsets(nums []int) [][]int {
	res := [][]int{{}}
	var backtrace func(index int, arr []int)
	backtrace = func(index int, arr []int) {
		for i := index; i < len(nums); i++ {
			tmp := append(append([]int{}, arr...), nums[i])
			res = append(res, append([]int{}, tmp...))
			backtrace(i+1, tmp)
		}
	}
	backtrace(0, []int{})
	return res
}

// 79
// https://leetcode-cn.com/problems/word-search/
func Exist(board [][]byte, word string) bool {
	var backtrace func(x, y, index int) bool
	backtrace = func(x, y, index int) bool {
		if index >= len(word) || board[x][y] != word[index] {
			return false
		}
		if index == len(word)-1 && board[x][y] == word[index] {
			return true
		}
		var tmp byte
		tmp, board[x][y] = board[x][y], tmp
		if x > 0 && backtrace(x-1, y, index+1) {
			return true
		}
		if x < len(board)-1 && backtrace(x+1, y, index+1) {
			return true
		}
		if y > 0 && backtrace(x, y-1, index+1) {
			return true
		}
		if y < len(board[0])-1 && backtrace(x, y+1, index+1) {
			return true
		}

		tmp, board[x][y] = board[x][y], tmp
		return false
	}

	for x := range board {
		for y := range board[x] {
			if board[x][y] == word[0] {
				if backtrace(x, y, 0) {
					return true
				}
			}
		}
	}
	return false
}

// 80
// https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii/
func RemoveDuplicates3(nums []int) int {
	pre, preN, index := -10001, 0, 0
	for i := 0; i < len(nums); i++ {
		if nums[i] != pre {
			nums[index], pre, preN, index = nums[i], nums[i], 1, index+1
		} else {
			if preN == 1 {
				nums[index], preN, index = nums[i], 2, index+1
			}
		}
	}
	return index
}

// 81
// https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/
func Search81(nums []int, target int) bool {
	n := len(nums)
	if n == 0 {
		return false
	}
	if n == 1 {
		return nums[0] == target
	}
	l, r, m := 0, n-1, 0
	for l <= r {
		m = (l + r) / 2
		if nums[m] == target {
			return true
		}
		if nums[m] == nums[l] && nums[m] == nums[r] {
			l, r = l+1, r-1
		} else if nums[l] <= nums[m] {
			if nums[l] <= target && target < nums[m] {
				r = m - 1
			} else {
				l = m + 1
			}
		} else {
			if nums[r] >= target && target > nums[m] {
				l = m + 1
			} else {
				r = m - 1
			}
		}
	}
	return false
}

// 82
// https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii
func DeleteDuplicates2(head *ListNode) *ListNode {
	var pre, cur, node *ListNode
	curN := 0
	node = head
	for node != nil {
		if cur != nil {
			if cur.Val != node.Val {
				if curN == 1 {
					if pre == nil {
						pre = cur
					} else {
						pre.Next = cur
						pre = pre.Next
					}
				} else {
					if pre == nil {
						head = node
					} else {
						pre.Next = node
					}
				}
				curN = 0
			}
		}
		cur, curN = node, curN+1
		node = node.Next
	}
	if curN != 1 {
		if pre == nil {
			head = nil
		} else {
			pre.Next = nil
		}
	}
	return head
}

// 83
// https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
func DeleteDuplicates(head *ListNode) *ListNode {
	if head != nil && head.Next != nil {
		var ptr = head
		for ptr.Next != nil {
			if ptr.Val == ptr.Next.Val {
				ptr.Next = ptr.Next.Next
			} else {
				ptr = ptr.Next
			}
		}
	}
	return head
}

// 84
//

// 85
//

// 86
// https://leetcode-cn.com/problems/partition-list/
func Prtition(head *ListNode, x int) *ListNode {
	var l, lh, g, gh *ListNode
	for head != nil {
		if head.Val < x {
			if l == nil {
				l, lh = head, head
			} else {
				l.Next = head
				l = l.Next
			}
		} else {
			if g == nil {
				g, gh = head, head
			} else {
				g.Next = head
				g = g.Next
			}
		}
		head, head.Next = head.Next, nil
	}
	if l == nil {
		lh, gh = gh, nil
	}
	if gh != nil && l != nil {
		l.Next = gh
	}
	return lh
}

// 87
//

// 88
// https://leetcode-cn.com/problems/merge-sorted-array/
func Merge(nums1 []int, m int, nums2 []int, n int) {
	var left, right = m - 1, m + n - 1
	for i := n - 1; i >= 0; i-- {
		for left >= 0 {
			if nums2[i] > nums1[left] {
				nums1[right] = nums2[i]
				right--
				break
			} else {
				nums1[right] = nums1[left]
				right--
				left--
			}
		}
		if left < 0 {
			nums1[right] = nums2[i]
			right--
		}
	}
}

// 89
// https://leetcode-cn.com/problems/gray-code
func GrayCode(n int) []int {
	var gen func(n int) []int
	gen = func(n int) []int {
		if n == 0 {
			return []int{0}
		}
		tmp := gen(n - 1)
		length := len(tmp)
		for i := length - 1; i >= 0; i-- {
			tmp = append(tmp, tmp[i]|1<<(uint(n)-1))
		}
		return tmp
	}
	return gen(n)
}

// 90
// https://leetcode-cn.com/problems/subsets-ii
func SubsetsWithDup(nums []int) [][]int {
	sort.Ints(nums)
	res := [][]int{{}}
	var backtrace func(index int, arr []int)
	backtrace = func(index int, arr []int) {
		for i := index; i < len(nums); i++ {
			if i > index && nums[i] == nums[i-1] {
				continue
			}
			tmp := append(append([]int{}, arr...), nums[i])
			res = append(res, append([]int{}, tmp...))
			backtrace(i+1, tmp)
		}
	}
	backtrace(0, []int{})
	return res
}

// 91
// https://leetcode-cn.com/problems/decode-ways/
func NumDecodings(s string) int {
	calcR := map[int]int{0: 1, 1: 1, 2: 2, 3: 3}
	var calc func(num int) int
	calc = func(num int) int {
		if v, ok := calcR[num]; ok {
			return v
		}
		calcR[num] = calc(num-1) + calc(num-2)
		return calcR[num]
	}
	var pre rune
	count, res := 0, 1
	for _, v := range s {
		switch v {
		case '0':
			if count == 0 {
				return 0
			}
			res, count = res*calc(count-1), 0
		case '1':
			fallthrough
		case '2':
			count++
		case '3':
			fallthrough
		case '4':
			fallthrough
		case '5':
			fallthrough
		case '6':
			res, count = res*calc(count+1), 0
		case '7':
			fallthrough
		case '8':
			fallthrough
		case '9':
			if pre == '1' {
				res, count = res*calc(count+1), 0
			} else {
				res, count = res*calc(count), 0
			}
		}
		pre = v
	}
	return res * calc(count)
}

// 92
// https://leetcode-cn.com/problems/reverse-linked-list-ii/
func ReverseBetween(head *ListNode, left int, right int) *ListNode {
	var reverse = func(head *ListNode, length int) *ListNode {
		var pre *ListNode
		index, ln := 1, head
		for index <= length && ln != nil {
			if pre == nil {
				pre, ln, ln.Next = ln, ln.Next, nil
			} else {
				pre, ln, ln.Next = ln, ln.Next, pre
			}
			index++
		}
		if ln != nil {
			head.Next = ln
		}
		return pre
	}
	if left > 1 {
		ln := head
		for i := 2; i < left; i++ {
			ln = ln.Next
		}
		if ln != nil {
			ln.Next = reverse(ln.Next, right-left+1)
		}
		return head
	} else {
		return reverse(head, right)
	}
}

// 93
// https://leetcode-cn.com/problems/restore-ip-addresses/
func RestoreIpAddresses(s string) []string {
	var res []string
	var backtrace func(index, num int, ip []byte)
	backtrace = func(index, num int, ip []byte) {
		if len(ip) == len(s)+3 {
			res = append(res, string(ip))
		} else if index < len(s) && num > 0 {
			if num < 4 {
				ip = append(ip, '.')
			}
			for i := index; i < len(s) && i < index+3; i++ {
				n, _ := strconv.Atoi(s[index : i+1])
				if n <= 255 && (i == index || s[index] != '0') {
					backtrace(i+1, num-1, append(ip, s[index:i+1]...))
				}
			}
		}
	}
	backtrace(0, 4, []byte{})
	return res
}

// 94
// https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
func InOrderTraversal(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	var nums []int
	if root.Left != nil {
		nums = append(nums, InOrderTraversal(root.Left)...)
	}
	nums = append(nums, root.Val)
	if root.Right != nil {
		nums = append(nums, InOrderTraversal(root.Right)...)
	}
	return nums
}

// 95
// https://leetcode-cn.com/problems/unique-binary-search-trees-ii/
func GenerateTrees(n int) []*TreeNode {
	if n == 0 {
		return nil
	}
	var generateTrees func(l, r int) []*TreeNode
	generateTrees = func(l, r int) []*TreeNode {
		if l > r {
			return []*TreeNode{nil}
		}
		var res []*TreeNode
		for i := l; i <= r; i++ {
			var leftTrees, rightTrees = generateTrees(l, i-1), generateTrees(i+1, r)
			for _, leftNode := range leftTrees {
				for _, rightNode := range rightTrees {
					res = append(res, &TreeNode{i, leftNode, rightNode})
				}
			}
		}
		return res
	}
	return generateTrees(1, n)
}

// 96
// https://leetcode-cn.com/problems/unique-binary-search-trees/
func NumTrees(n int) int {
	var sum = 0
	var generateTrees func(l, r int) int
	var length = make(map[int]int)
	generateTrees = func(l, r int) int {
		if l > r {
			return 1
		}
		if v, ok := length[r-l]; ok {
			return v
		}
		var sum = 0
		for i := l; i <= r; i++ {
			sum += generateTrees(l, i-1) * generateTrees(i+1, r)
		}
		length[r-l] = sum
		return sum
	}
	for i := 1; i <= n/2; i++ {
		sum += generateTrees(1, i-1) * generateTrees(i+1, n)
	}
	sum *= 2
	if n%2 == 1 {
		sum += generateTrees(1, n/2) * generateTrees(n/2+2, n)
	}
	return sum
}

// 97
// https://leetcode-cn.com/problems/interleaving-string/
func IsInterleave(s1 string, s2 string, s3 string) bool {
	m, n, t := len(s1), len(s2), len(s3)
	if (m + n) != t {
		return false
	}
	f := make([][]bool, m+1)
	for i := 0; i <= m; i++ {
		f[i] = make([]bool, n+1)
	}
	f[0][0] = true
	for i := 0; i <= m; i++ {
		for j := 0; j <= n; j++ {
			p := i + j - 1
			if i > 0 {
				f[i][j] = f[i][j] || (f[i-1][j] && s1[i-1] == s3[p])
			}
			if j > 0 {
				f[i][j] = f[i][j] || (f[i][j-1] && s2[j-1] == s3[p])
			}
		}
	}
	return f[m][n]
}

// 98
// https://leetcode-cn.com/problems/validate-binary-search-tree/
func IsValidBST(root *TreeNode) bool {
	var isValid func(root *TreeNode, min int, max int) bool
	isValid = func(root *TreeNode, min int, max int) bool {
		if root == nil {
			return true
		}
		if root.Val <= min || root.Val >= max {
			return false
		}
		return isValid(root.Left, min, root.Val) && isValid(root.Right, root.Val, max)
	}
	return isValid(root, math.MinInt64, math.MaxInt64)
}

// 99
//

// 100
// https://leetcode-cn.com/problems/same-tree/
func IsSameTree(p *TreeNode, q *TreeNode) bool {
	if p == nil && q == nil {
		return true
	}
	if p != nil && q != nil {
		if p.Val != q.Val {
			return false
		}
		return IsSameTree(p.Left, q.Left) && IsSameTree(p.Right, q.Right)
	}
	return false
}
